#include <iostream>
using namespace std;
/*
void swap(char &a, char &b)
{
	if(a==b)
		return;
	a ^= b;
	b ^= a;
	a ^= b;
}
*/
void q_sort(char str[], int l, int h)
{
	if(l >= h)
		return;
	int i = l;
	//i及i之前均小于等于首元素，i之后j之前均大于首元素
	for(int j=i+1; j<=h; j++)
	{
		if(str[j] <= str[l])
		{
			++i;
			swap(str[i], str[j]);
		}
	}
	swap(str[l], str[i]);
	q_sort(str, l, i-1);
	q_sort(str, i+1, h);
}

//在元素相同时仍能保持nlogn
void q_sort2(char str[], int l, int h)
{
	if(l >= h)
		return;
	int i = l+1;
	int j = h;
	//i之前均小于等于首元素，j之后均小于等于首元素
	while(1)
	{
		while(i < h && str[i] < str[l])
			i++;
		while(str[j] > str[l])
			j--;
		if(i >= j)
			break;
		swap(str[i], str[j]);
		i++;
		j--;
	}
	swap(str[j], str[l]);
	q_sort2(str, l, j-1);
	q_sort2(str, j+1, h);
}

int main()
{
	char str[] = "wangureyfuckyou";
	q_sort(str, 0, 14);
	cout<<str<<endl;
	char str2[] = "wangureyfuckyou";
	q_sort2(str2, 0, 14);
	cout<<str2<<endl;
	return 0;
}
